package ia1011.zanzibar.processor.fsm;

import ia1011.zanzibar.featurestructures.FeatureStructure;
import ia1011.zanzibar.rules.AltElem;
import ia1011.zanzibar.rules.FSRegEx;
import ia1011.zanzibar.rules.KleeneElem;
import ia1011.zanzibar.rules.RegExElem;
import ia1011.zanzibar.rules.Rule;

import java.util.*;

/**
 * The class represents a FSM built over feature structures
 * 
 * @author Alessandro Perrino (creator)
 * @author <br> Bastianelli E. emanuele.bastianelli@gmail.com (modifier)
 * @author <br> Caponi E. emiliano.caponi@gmail.com (modifier)
 * @author <br> Castellucci G. castellucci.giuseppe@gmail.com (modifier)
 * @author <br> Rossi A. berardino.viola@gmail.com (modifier)
 *  
 */

public class FSM {
	
	// The initial state of the FSM
	State initialState; 

	/**
	 * 
	 * @return the initial state of automaton
	 */
	public State getInitial() {
		return initialState;
	}

	/**
	 * Builds the non-deterministic FSM without void transitions accepting the regular expressions on the
	 * right hand side of the given rules 
	 * @param rules
	 * @throws Exception
	 */
	public FSM(Rule[] rules) throws Exception {
		initialState = new State();
		for (int i=0; i<rules.length; i++) {		
			FSM temp = new FSM(rules[i]);
			initialState.addTransition(new Transition(null, temp.getInitial()));
		}
		eliminateVoidTransitions();
	}

	/** 
	 * Builds the non-deterministic FSM with void transitions accepting the regular expression on the right
	 * hand side of the given rule
	 * @param rule
	 * @throws Exception
	 */
	public FSM(Rule rule) throws Exception {
		initialState = new State();
		FSRegEx regex = rule.getLhs();
		RegExElem currentElem;
		State currentState, nextState;
		State finalState = new State();
		currentState = initialState;
		Iterator iter = regex.getElements().iterator();
		// for each element of the regular expression a transition (simple or complex) is built
		while (iter.hasNext()) {
			currentElem = (RegExElem)iter.next();
			// each element of the FSM is separated by void transitions through an insulator state
			State insulator = new State();
			currentState.addTransition(new Transition(null,insulator));
			currentState = insulator;
			if (currentElem instanceof FeatureStructure) {
				//the easy case
				nextState = new State();
				currentState.addTransition(new Transition((FeatureStructure)currentElem, nextState));
				currentState = nextState;
			} else {
				// the current pattern is a complex pattern element
				// ..it will probaly be converted into a sequence of states itself.
				currentState =  buildComplexTransition(currentState,currentElem);
			}
		}
		//link the end of the current pattern to the final state using
		//an empty transition.
		currentState.addTransition(new Transition(null,finalState));
		finalState.setFinal();
		finalState.setRule(rule);
	}

	/**
	 * Builds a non-deterministic FSM with void transitions starting from the given initial state and accepting the given
	 * complex constituent (that is, either a regular expression followed by a Kleene operator or a set of alternative 
	 * regular expressions). Returns the final state of the FSM. 
	 *
	 * @param initialState
	 * @param pattern
	 * @return
	 * @throws Exception
	 */
	public State buildComplexTransition(State initialState, RegExElem pattern) throws Exception {
		State currentState = null;
		State nextState;
		State finalState = new State();
		RegExElem currentElem;
		Iterator iter;
		if (pattern instanceof KleeneElem) {
			// the element is a regular espression followed by a kleene operator
			FSRegEx regex = ((KleeneElem)pattern).getBody();
			iter = regex.getElements().iterator();
			// for each element of the regular expression a transition (simple or complex) is built
			while (iter.hasNext()) {
				currentElem = (RegExElem)iter.next();
				if (currentState == null)
					currentState = initialState; 
				// each element of the FSM is separated by void transitions through an insulator state
				State insulator = new State();
				currentState.addTransition(new Transition(null,insulator));
				currentState = insulator;
				if(currentElem instanceof FeatureStructure) {
					//the easy case
					nextState = new State();
					currentState.addTransition(new Transition((FeatureStructure)currentElem, nextState));
					currentState = nextState;
				}  else {
					// the current pattern is a complex pattern element
					// ..it will probaly be converted into a sequence of states itself.
					currentState =  buildComplexTransition(currentState,currentElem);
				}
			} // for i
			//link the end of the current pattern to the final state using
			//an empty transition.
			currentState.addTransition(new Transition(null,finalState));
			//let's consider the kleene operator
			char c = ((KleeneElem)pattern).getOp();
			if (c == '?') {
				// allow to skip everything via a null transition
				initialState.addTransition(new Transition(null,finalState));
			} else if (c == '+') {
				// allow to return to initialState
				finalState.addTransition(new Transition(null,initialState));
			} else if (c == '*') {
				// allow to skip everything via a null transition
				initialState.addTransition(new Transition(null,finalState));
				// allow to return to initialState
				finalState.addTransition(new Transition(null,initialState));
			} else
				throw new Exception("Invalid Kleene operator!");
		} else if (pattern instanceof AltElem) {
			// the element is a set of alternative regular expressions
			// each one produces a different FSM, with the final state in common
			Iterator altIter = ((AltElem)pattern).getElements().iterator();
			while (altIter.hasNext()) {
				FSRegEx regex = (FSRegEx)altIter.next();
				iter = regex.getElements().iterator();
				// for each element of the regular expression a transition (simple or complex) is built
				while (iter.hasNext()) {
					currentElem = (RegExElem)iter.next();
					currentState = initialState;
					// each element of the FSM is separated by void transitions through an insulator state
					State insulator = new State();
					currentState.addTransition(new Transition(null,insulator));
					currentState = insulator;
					if(currentElem instanceof FeatureStructure) {
						//the easy case
						nextState = new State();
						currentState.addTransition(new Transition((FeatureStructure)currentElem, nextState));
						currentState = nextState;
					} else {
						// the current pattern is a complex pattern element
						// ..it will probaly be converted into a sequence of states itself.
						currentState =  buildComplexTransition(currentState,currentElem);
					}
				} // for i
				//link the end of the current pattern to the final state using
				//an empty transition.
				currentState.addTransition(new Transition(null,finalState));
			} // for j
		} else
			throw new Exception("Invalid element in the regular expression");
		return finalState;
	}

	/**
	 * Computes and returns the epsilon closure of the given set of states, that is the set of states that are 
	 * accessible from any of the states in the given set using only void transitions.	 *
	 * @param s
	 * @return
	 */
	private AbstractSet epsilonClosure(AbstractSet s) {
		// the stack/queue used by the algorithm
		LinkedList list = new LinkedList(s);
		// the set to be returned
		AbstractSet epsilonClosure = new HashSet(s);
		State top;
		Iterator transIter;
		Transition currentTransition;
		State currentState;
		while (!list.isEmpty()) {
			top = (State)list.removeFirst();
			transIter = top.getTransitions().iterator();
			while(transIter.hasNext()) {
				currentTransition = (Transition)transIter.next();
				if(currentTransition.getConstraint() == null) {
					currentState = currentTransition.getTarget();
					if(!epsilonClosure.contains(currentState)) {
						epsilonClosure.add(currentState);
						list.addFirst(currentState);
					}
				}
			}
		}
		return epsilonClosure;
	}

	/**
	 * Converts this FSM from a non-deterministic to a deterministic one by 
	 * eliminating all the unrestricted transitions. 
	 * @throws Exception
	 */
	public void eliminateVoidTransitions() throws Exception {
		Map newStates = new HashMap();
		Set dStates = new HashSet();
		LinkedList unmarkedDStates = new LinkedList();
		AbstractSet currentDState = new HashSet();
		currentDState.add(initialState);
		currentDState = epsilonClosure(currentDState);
		dStates.add(currentDState);
		unmarkedDStates.add(currentDState);
		// create a new state that will take the place the set of states
		// in currentDState
		initialState = new State();
		newStates.put(currentDState, initialState);
		// find out if the new state is a final one
		Iterator innerStatesIter = currentDState.iterator();
		Rule action = null;
		while (innerStatesIter.hasNext()) {
			State currentInnerState = (State)innerStatesIter.next();
			if (currentInnerState.isFinal()) {
				initialState.setFinal();
				action = currentInnerState.getRule();
				initialState.setRule(action);
			}
		}
		while (!unmarkedDStates.isEmpty()) {
			currentDState = (AbstractSet)unmarkedDStates.removeFirst();
			Iterator insideStatesIter = currentDState.iterator();
			while (insideStatesIter.hasNext()) {
				State innerState = (State)insideStatesIter.next();
				Iterator transIter = innerState.getTransitions().iterator();
				while (transIter.hasNext()) {
					Transition currentTrans = (Transition)transIter.next();
					if (currentTrans.getConstraint() !=null) {
						State target = currentTrans.getTarget();
						AbstractSet newDState = new HashSet();
						newDState.add(target);
						newDState = epsilonClosure(newDState);
						if (!dStates.contains(newDState)) {
							dStates.add(newDState);
							unmarkedDStates.add(newDState);
							State newState = new State();
							newStates.put(newDState, newState);
							//find out if the new state is a final one
							innerStatesIter = newDState.iterator();
							while (innerStatesIter.hasNext()) {
								State currentInnerState = (State)innerStatesIter.next();
								if (currentInnerState.isFinal()) {
									newState.setFinal();
									newState.setRule(currentInnerState.getRule());
								}
							}
						}
						State currentState = (State)newStates.get(currentDState);
						State newState = (State)newStates.get(newDState);
						currentState.addTransition(new Transition(currentTrans.getConstraint(),	newState));
					}
				}
			}
		}
	}

	/** 
	 * Prints a simple representation of a FSM. 
	 */
	public void display() {
		initialState.display(0);
	}
}
